#ifndef RANDOMPERMUTATION_HPP
#define RANDOMPERMUTATION_HPP
#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */
#include <iostream>
#include <algorithm>


class RandomPermutation
{
public:
    //fisher-yates shuffle
    template<typename T>
    static void FYShuffle(T *index, size_t count, size_t nShuffle)
    {
        for(size_t i=0;i<nShuffle;i++)
        {
            size_t j=rand()%(count-i)+i;
            T tmp=index[i];
            index[i]=index[j];
            index[j]=tmp;
        }
    }

    static size_t RecoverIndex(size_t in, const size_t *seg, size_t n)
    {
        for(size_t i=0;i<n;i++)
        {
            if(in<seg[i])
                return in+i;
        }
        return in;
    }

    static void ChooseRandom(size_t *index, size_t nTotal, size_t nSelect)
    {
        for(size_t i=0;i<nSelect;i++)
            index[i]=rand()%(nTotal-i);

        for(size_t i=1;i<nSelect;i++)
        {
            index[i]=RecoverIndex(index[i],index,i);
            std::inplace_merge(index,index+i,index+i+1);
        }
    }

    static int Compare(const size_t *index1, const size_t *index2, size_t nSelect)
    {
        for(size_t i=0;i<nSelect;i++)
        {
            if(index1[i]<index2[i])
                return -1;
            if(index1[i]>index2[i])
                return 1;
        }
        return 0;
    }

    //given index[0...nLast-1] in ascending order
    //if index[nLast] == index[0...nLast-1], return false
    static bool Merge(size_t **index, size_t nSelect, size_t nLast)
    {
        size_t *refIndex=index[nLast];
        size_t j=0;
        for(;j<nLast;j++)
        {
            int res=Compare(refIndex,index[j],nSelect);
            if(res==0)
                return false;
            if(res<0)
                break;
        }

        for(size_t i=nLast;i>j;i--)
        {
            index[i]=index[i-1];
        }

        index[j]=refIndex;

        return true;
    }

    static size_t MaxSetCount(size_t nTotal, size_t nSelect)
    {
        if(nSelect==0)
            return 1;
        return MaxSetCount(nTotal, nSelect-1)*(nTotal+1-nSelect)/nSelect;
    }

    static void dp(size_t **index, size_t nSelect, size_t nSet)
    {
        for(size_t i=0;i<nSet;i++)
        {
            for(size_t j=0;j<nSelect;j++)
                std::cout<<index[i][j]<<'\t';
            std::cout<<'\n';
        }
        std::cout<<'\n'<<std::flush;
    }

protected:
    size_t nSet;

public:
    size_t **index;

public:
    RandomPermutation(size_t nSet0)
        : nSet(nSet0)
        , index(NULL)
    {

        /* initialize random seed: */
        srand (time(NULL));
    }

    ~RandomPermutation()
    {
        Release();
    }

    void Release()
    {
        if(index!=NULL)
        {
            for(size_t i=0;i<nSet;i++)
                delete [] index[i];
            delete []index;
            index=NULL;
        }
    }

    size_t Generate(size_t nTotal, size_t nSelect)
    {
        Release();

        if(nTotal<nSelect)
            return 0;

        size_t n=MaxSetCount(nTotal,nSelect);
        if(nSet>n)
            nSet=n;


        index=new size_t*[nSet];
        for(size_t i=0;i<nSet;i++)
            index[i]=new size_t[nSelect];

        ChooseRandom(index[0],nTotal,nSelect);
        //        dp(index,nSelect,nSet);
        for(size_t i=1;i<nSet;)
        {
            ChooseRandom(index[i],nTotal,nSelect);
            if(Merge(index,nSelect,i))
                i++;
            //            dp(index,nSelect,nSet);
        }

        return nSet;
    }

};
#endif // RANDOMPERMUTATION_HPP
